package demo2;

public class MyListed {
    static class Node {
        private int val;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;

    //创建链表
    public void creatList() {
        Node node1 = new Node(12);
        Node node2 = new Node(13);
        Node node3 = new Node(14);
        Node node4 = new Node(13);
        Node node5 = new Node(12);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

    //遍历输出链表
    public void display() {
        Node cur = this.head;
        while (cur != null) {
            System.out.println(cur.next + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表的中间节点
    public Node middleNode() {
        if (head == null) {
            return null;
        }
        Node fast = this.head;
        Node slow = this.head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;

    }

    //单链表的逆置
    public Node reverseList() {
        if (head == null) {
            return null;
        }
        Node cur = head.next;
        Node curNext;
        head.next = null;
        while (cur != null) {
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }


    //链表中倒数第K个结点
    public Node FindKthToTail(int k) {
        if (head == null) {
            return null;
        }
        if (k <= 0) {
            return null;
        }
        Node fast = this.head;
        Node slow = this.head;

        //先让fast走k-1步
        while (--k > 0) {
            fast = fast.next;
            if (fast == null) {  //用来代替判断  k>size
                return null;
            }
        }

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

    //合并两个有序链表
    public Node mergeTwoLists(Node list1, Node list2) {
        Node head = new Node(-1);
        Node cur = head;
        while ((list1 != null) && (list2 != null)) {
            if (list1.val < list2.val) {
                cur.next = list1;
                cur = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }

        if (list2 != null) {
            cur.next = list2;
        }
        if (list1 != null) {
            cur.next = list1;
        }

        return head.next;


    }

    //判断链表回文
    public boolean chkPalindrome(Node A) {
        if (A == null) {
            return false;
        }
        Node fast = A;
        Node slow = A;

        //先找中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //将后半部分逆置
        Node cur = slow.next;
        Node curNext;

        while (cur != null) {
            curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }


        Node head1 = A;
        //slow 和 头结点  同时往中间走
        while (slow != head1) {
            if (slow.val != head1.val) {
                return false;
            }
            if (head1.next == slow) {
                return true;
            }
            slow = slow.next;
            head1 = head1.next;
        }

        return true;



    }



}


